package 剑指Offer专项突破;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @Author zhang lei
 * @Date 2021-12-01 19:52
 * 排序
 */
public class Algo74 {
    public static void main(String[] args) {
        int[][] arr = {{1,3},{8,10},{2,6},{15,18}};
        printArr(merge(arr));

        //这个比较要会
        Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));

        printArr(arr);
    }

    private static void printArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i][0] + ":" + arr[i][1]);
        }
    }

    /**
     * 排序
     * @param intervals
     * @return
     */
    public static int[][] merge(int[][] intervals) {

        //先排序
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i+1; j < intervals.length; j++) {
                if(intervals[j][0]<intervals[i][0]) {
                    swapElement(intervals, i, j);
                }
            }
        }
        List<Integer[]> result = new ArrayList<>();
        List<Integer> cur = new ArrayList<>(2);
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if(cur.size() == 0) {
                cur.add(start);
                cur.add(end);
            }else {
                if(start>cur.get(cur.size()-1)) {
                    result.add(new Integer[]{cur.get(0), cur.get(1)});
                    cur.clear();
                    cur.add(start);
                    cur.add(end);
                }else if(end>cur.get(cur.size()-1)) {
                    cur.remove(1);
                    cur.add(end);
                }
            }

            if(i == intervals.length -1) {
                result.add(new Integer[]{cur.get(0), cur.get(1)});
            }
        }

        int[][] r = new int[result.size()][2];
        for (int i = 0; i < result.size(); i++) {
            r[i] = new int[]{result.get(i)[0], result.get(i)[1]};
        }
        return r;
    }

    private static void swapElement(int[][] intervals, int i, int j) {
        int[] temp = intervals[i];
        intervals[i] = intervals[j];
        intervals[j] = temp;
    }
}
